package com.yangzhe.algorithm.c037;

// 二叉树打家劫舍问题
// 测试链接 : https://leetcode.cn/problems/house-robber-iii/
public class Code07_MyHouseRobberIII {

    // 不提交这个类
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

    /**
     * 思路：DFS（后续遍历）+动态规划
     * 状态转移：
     * 当前root节点只有偷与不偷两种状态：
     * 数组 0位置代表不偷当前root时能偷的最大金额
     * 数组 1位置代表偷当前root时能偷的最大金额
     * <p>
     * 1. 偷当前root
     * 左右节点都不能偷
     * curMax = root.val + left[0] + right[0]
     * 2. 不偷当前root
     * 左右节点可偷可不偷
     * curMax = max(left[0], left[1]) + max(right[0], right[1])
     * <p>
     * 算法流程：
     * 从上述过程可以看出，当前节点的值取决于左、右子树的值
     * 所以使用后续遍历，利用后续遍历回溯特性（处理完左右子树，再处理根）
     *
     * @param root
     */
    public int rob(TreeNode root) {
        int[] rootValue = dfsPostOrder(root);

        return Math.max(rootValue[0], rootValue[1]);
    }

    public static int[] dfsPostOrder(TreeNode root) {
        int[] cur = new int[2];

        // base case 遍历到底了
        if (root == null) {
            return cur;
        }

        int[] left = dfsPostOrder(root.left);
        int[] right = dfsPostOrder(root.right);


        // 不偷当前节点
        cur[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        // 偷当前节点
        cur[1] = root.val + left[0] + right[0];

        return cur;
    }
}
